package leet;

import common.TreeNode;
import common.Util;
import org.junit.Test;

import java.util.*;

/**
 * @author fance
 * @date 18-5-4 上午10:27
 */
public class OneToTwoHundred {

    /**
     * 1. Two Sum
     * 1.bf 2.排序 双指针 3.hashmap记录
     * @param nums
     * @param target
     * @return
     */
    public int[] twoSumI(int[] nums, int target) {
        int[] res = new int[2];
        Arrays.sort(nums);
        int i = 0;
        int j = nums.length - 1;
        int cur;
        while (i < j) {
            cur = nums[i] + nums[j];
            if (cur == target) {
                res[0] = i;
                res[1] = j;
                return res;
            } else if (cur > target) {
                j--;
            } else {
                i++;
            }
        }
        return null;
    }
    public int[] twoSumII(int[] nums, int target) {
        int[] res = new int[2];
        Map<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                res[0] = map.get(nums[i]);
                res[1] = i;
                return res;
            } else {
                map.put(target - nums[i], i);
            }
        }
        return null;
    }

    /**
     * 9. 回文数
     * @param x
     * @return
     */
    public boolean isPalindrome(int x) {
        return Util.isPalindrome(String.valueOf(x));
    }

    /**
     * 14. 最长公共前缀
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length < 1) {
            return "";
        }
        String minLenS = "";
        int minLen = Integer.MAX_VALUE;
        for (String cur : strs) {
            if (cur.length() < minLen) {
                minLen = cur.length();
                minLenS = cur;
            }
        }
        String res = "";
        for (int i = 1; i <= minLenS.length(); i++) {
                String tmp = minLenS.substring(0,i);
                if (isStartWith(strs,tmp) && tmp.length() > res.length()) {
                    res = tmp;
            }
        }
        return res;
    }
    private boolean isStartWith(String[] strs,String s){
        for (int i = 0; i < strs.length; i++) {
            if (!strs[i].startsWith(s)) {
                return false;
            }
        }
        return true;
    }
    /**
     * 20. 有效的括号
     * @param s
     * @return
     */
    public static boolean isValid(String s) {
        if (s == null) {
            return true;
        }
        LinkedList<Character> stack = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            if (stack.isEmpty()) {
                stack.push(s.charAt(i));
                continue;
            }
            if ((s.charAt(i) == ')' && stack.peek() == '(')
                    || (s.charAt(i) == ']' && stack.peek() == '[')
                    ||(s.charAt(i) == '}' && stack.peek() == '{')) {
                stack.pop();
            } else {
                stack.push(s.charAt(i));
            }

        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        String[] a = new String[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.next();
        }
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j) {
                     if (isValid(a[i] + a[j])) {
                         cnt++;
                     }
                } else if (isValid(a[i] + a[j])) {
                    cnt++;
                }
            }
        }
        System.out.println(cnt);
    }
    /**
     * 22. 括号生成
     * @param n
     * @return
     */
    public List<String> generateParenthesis(int n) {
        char[] str = new char[n * 2];
        List<String> list = new LinkedList<>();
        addParen(list,n,n,str,0);
        return list;
    }
    private void addParen(List<String> list, int leftRem,
                          int rightRem,char[] str, int count) {
        if (leftRem < 0 || rightRem < leftRem) {
            return;
        }
        if (leftRem == 0 && rightRem == 0) {
            list.add(String.valueOf(str));
        } else {
            if (leftRem > 0) {
                str[count] = '(';
                addParen(list,leftRem - 1,rightRem,str,count + 1);
            }

            if (rightRem > leftRem) {
                str[count] = ')';
                addParen(list,leftRem,rightRem - 1,str,count + 1);
            }
        }
    }


    /**
     * 118. 杨辉三角
     * @param numRows
     * @return
     */
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        if (numRows < 1) {
            return res;
        }
        for (int i = 0; i < numRows; i++) {
            List<Integer> cur = new ArrayList<>();
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    cur.add(1);
                } else {
                    cur.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
                }
            }
            res.add(cur);
        }
        return res;
    }

    /**
     * 70. 爬楼梯
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        if (n < 1) {
            return 0;
        }
        if (n < 4) {
            return n;
        }
        int pre = 2;
        int prepre = 1;
        int res = 0;
        for (int i = 3; i <= n; i++) {
            res = pre + prepre;
            prepre = pre;
            pre = res;
        }
        return res;
    }

    /**
     * 101. 对称二叉树
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        return isSymmetricCore(root.left,root.right);
    }
    private boolean isSymmetricCore(TreeNode root1,TreeNode root2) {
        if (root1 == null && root2 == null) {
            return true;
        }
        if (root1 == null || root2 == null) {
            return false;
        }
        if (root1.val != root2.val) {
            return false;
        }
        return isSymmetricCore(root1.left,root2.right) && isSymmetricCore(root1.right,root2.left);

    }

    /**
     * 64. Minimum Path Sum
     * @param grid
     * @return
     */
    public int minPathSum(int[][] grid) {
        if (grid == null || grid.length < 1) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m][n];
        dp[0][0] = grid[0][0];
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + grid[0][i];
        }
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j],dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * 62. Unique Paths
     * @param m
     * @param n
     * @return
     */
    public int uniquePaths(int m, int n) {
        if (m < 1 || n < 1) {
            return 1;
        }
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     *
     * @param m
     * @param n
     * @return
     */
    public int uniquePathsII(int[][] obstacleGrid) {
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        if (m < 1 || n < 1) {
            return 1;
        }
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            if (obstacleGrid[i][0] == 1) {
                break;
            }
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            if (obstacleGrid[0][i] == 1) {
                break;
            }
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] != 1) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m - 1][n - 1];
    }

    /**
     * 120. Triangle  TODO
     * @param triangle
     * @return
     */
    public int minimumTotal(List<List<Integer>> triangle) {
        if (triangle == null || triangle.get(0) == null) {
            return 0;
        }
        return 0;
    }
    @Test
    public void test() {
       /* System.out.println(isValid("()"));
        System.out.println(isValid("(])"));
        System.out.println(isValid("({[]})"));
        System.out.println(isValid(""));*/
        /*  int[] a = {2, 7, 11, 15};
        int[] res = twoSumII(a,9);
        System.out.println(res[0] + " " + res[1]);*/


       /* System.out.println(isPalindrome(121));
        System.out.println(isPalindrome(-121));
        System.out.println(isPalindrome(10));*/
       /* String[] strings1 = {"ca","a"};
        String[] strings2 = {"dog","racecar","car"};
        System.out.println(longestCommonPrefix(strings1));*/
       // System.out.println(longestCommonPrefix(strings2));

        /*System.out.println(uniquePaths(3,2));
        System.out.println(uniquePaths(7,3));*/

        int[][] grid = {
                {0, 0, 0},
        {0, 1, 0},
            {0, 0, 0}
};

        System.out.println(uniquePathsII(grid));

    }
}
